import java.util.Arrays;

public class Test2 {
    public int wiggleMaxLength(int[] nums) {
        //动态规划，第i个位置的状态可以细分为下降状态和上升状态，我们无法通过前面的状态来知道当前上升或者下降状态是否符合摆动序列，所以就多创建出一行dp[i][0]表示当前状态为上升状态时的最长摆动序列，dp[i][1]表示当前状态为下降状态时的最长摆动序列
        //状态转移方程：如果当前状态为上升状态，那么dp[i][0] = dp[i-1][1] + 1;dp[i][1] = 1;
        //如果当前状态为下降状态，那么dp[i][1] = dp[i-1][0] + 1,dp[i][0] = 1
        int n = nums.length;
        int[][] dp = new int[2][n];
        Arrays.fill(dp[0],1);
        Arrays.fill(dp[1],1);
        int ret = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[0][i] = Math.max(dp[1][j] + 1,dp[0][i]);
                }else if (nums[i] < nums[j]) {
                    dp[1][i] = Math.max(dp[0][j] + 1,dp[1][i]);
                }
                ret = Math.max(ret,Math.max(dp[0][i],dp[1][i]));
            }
        }
        return ret;
    }
}
